package demo1;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

public class Test {
    public static void main(String[] args) {
        int[] array = {1,5,43,3,2,7,98,41,567,78};
        int[] ret = maxK(array,3);
        System.out.println(Arrays.toString(ret));


    }
    //时间复杂度 : n*logk
    public static int[] maxK(int[] arr, int k) {
        int[] ret = new int[k];
        if(arr == null || k == 0) {
            return ret;
        }
        Queue<Integer> minHeap = new PriorityQueue<>(k);

        //放前k个数到堆中
        //时间复杂度 : k * logk
        for (int i = 0; i < k; i++) {
            minHeap.offer(arr[i]);
        }
        //遍历剩下的K-1个,每次和堆顶元素进行比较
        // 堆顶元素 小的时候, 就出堆 .   (N - k) * logk
        for (int i = k; i < arr.length; i++) {
            if (arr[i] > minHeap.peek()) {
                minHeap.poll();
                minHeap.offer(arr[i]);
            }
        }
        int i = 0;
        while(!minHeap.isEmpty()) {
            ret[i++] = minHeap.poll();
        }
        return ret;
    }
    public void swap(int x, int[] arr, Queue minHeap) {

    }
    public int[] smallestK1(int[] arr, int k) {
        int[] ret = new int[k];
        if (arr == null || k == 0) {
            return ret;
        }
        Queue<Integer> minHeap = new PriorityQueue<>();
        for (int x : arr) {
            minHeap.offer(x);
        }

        for (int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();
        }
        return ret;
    }

}
